1. Field of the Invention
The invention relates to sequence generators and to the secure transmission of digital data within communication systems. More particularly, the present invention relates to the generation of cryptographically secure pseudo-random sequences suitable for fast encryption of digital data within communication systems.
2. Description of Prior Art
The security of many cryptographic systems depends upon the generation of unpredictable quantities that must be of sufficient size and random. Linear feedback shift registers (LFSRs) are a well-known and widely used basic component for the generation of a pseudo-random sequence having a long period and good statistical properties.
However, there exists a linear relation in a subsequence generated according to the LFSR method. Therefore, the initial value and the generating polynomial of the LFSR can be estimated by solving simultaneous linear equations obtained from a subsequence of the pseudo-random sequence generated according to the LFSR method.
To avoid this linearity problem, a combining function, whose inputs are taken from the outputs of several LFSRs in parallel, is used to destroy the linearity of the original sequence generated according to the LFSRs. In convention, the combining function employed is a fixed function. Therefore, the mapping defined by the combining function is a one-to-one mapping, and for the same input imposed on the combining function, the same output will be obtained. Such a generator suffers a divide-and-conquer attack if a correlation exists between the pseudo-random sequence and the output sequence of individual LFSRs. One solution could be to use the Data Encryption Standard (DES) to randomize the output but this is not economical as a substantial amount of hardware is required.
Generally stated, problems arise because pseudo-random sequence generators based on LFSRs are cryptographically unsafe and a substantial amount of hardware has to be used to make it safe.